#include <queue>
using namespace std;

//岛屿数量
class Solution1 {
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    bool array[300][300]={false};
    //typedef pair<int,int> PII;
    int m=0,n=0;
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();

        int ret = 0;
        for(int i =0;i<m;++i)
        {
            for(int j = 0;j<n;++j)
            {
                if('1' == grid[i][j] && !array[i][j])
                {
                    ++ret;
                    bfs(grid,i,j); //把这座岛屿中的陆地块全部标记
                }
            }
        }
        return ret;
    }
    void bfs(vector<vector<char>>& grid, int i,int j)
    {
        queue<pair<int,int>> q;
        q.push({i,j});
        array[i][j]=true;//
        while(!q.empty())
        {
            int a = q.front().first, b = q.front().second;
            q.pop();
            for(int k = 0;k<4;++k)
            {
                int x = a+dx[k], y = b+dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && '1' == grid[x][y] && !array[x][y])
                {
                    q.push({x,y});
                    array[x][y]=true;
                }
            }
        }
    }
};

//岛屿数量  DFS
array<int, 4> X = { -1,1,0,0 };
array<int, 4> Y = { 0,0,-1,1 };
void dfs(vector<vector<int>>& vv,int x,int y)
{
    vv[x][y] = 0;
    for (int i = 0;i < 4;++i)
    {
        int new_x = x + X[i];
        int new_y = y + Y[i];
        if (vv[new_x][new_y] == 1) {
            dfs(vv, new_x, new_y);
        }
    }
    return;
}
int Num(vector<vector<int>>& vv)
{
    int num = 0;
    int m = vv.size();
    int n = vv[0].size();
    for (int i = 0;i < m;++i)
    {
        for (int j = 0;j < n;++j)
        {
            if (vv[i][j] == 1)
            {
                ++num;
                dfs(vv, i, j);
            }
        }
    }
    return num;
}

//岛屿最大面积面积
class Solution2 {
public:
    //BFS
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    int array[50][50]={false};//如果题目要求不修改原二维数组的情况下要引入一个新数组，用来标记
    int ret = 0;

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if(grid.empty())
        return 0;
        int m = grid.size(),n=grid[0].size();
        for(int i = 0;i<m;++i)
        {
            for(int j = 0;j<n;++j)
            {
                if(1 == grid[i][j] && !array[i][j])
                {
                int tmp = bfs(grid,i,j); //将这座岛屿标记为true
                if(ret<tmp)
                {
                    ret = tmp;
                }
                }
            }
        }
        return ret;
    }
    int bfs(vector<vector<int>>& grid,int i,int j)
    {
        int m = grid.size(),n=grid[0].size();
        int cnt = 0;
        queue<pair<int,int>> q;
        q.push({i,j});
        array[i][j]=true;

        while(!q.empty())
        {
            int a = q.front().first;
            int b = q.front().second;
            q.pop();
            ++cnt;
            for(int k = 0;k<4;++k)
            {
                int x = a+dx[k];
                int y = b+dy[k];
                if(x>=0 && x<m && y>=0 && y<n && 1==grid[x][y] && !array[x][y])
                {
                    q.push({x,y});
                    array[x][y]=true;//当构成岛屿的土地进入队列，就将该土地坐标对应的array数组的值标记为true，不再入队列
                }
            }
        }
        return cnt;
    }
};

//被围绕的区域
class Solution3 {
public:
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    int n = 0,m = 0;
    void solve(vector<vector<char>>& board) {
        if(board.empty())
        return;
        int n = board.size();
        int m = board[0].size();
        //先扫描边缘区域
        for(int i = 0;i<m;i++)
        {
            if('O' == board[0][i])
            bfs(board,0,i);
            if('O' == board[n-1][i])
            bfs(board,n-1,i);
        }
        for(int j = 0;j<n;++j)
        {
            if('O' == board[j][0])
            bfs(board,j,0);
            if('O' == board[j][m-1]);
            bfs(board,j,m-1);
        }
        for(int i = 0;i<n;++i)
        {
            for(int j = 0;j<m;++j)
            {
                if('O' == board[i][j])
                board[i][j] = 'X';
                else if('.' == board[i][j])
                board[i][j] = 'O';
            }
        }

    }
    void bfs(vector<vector<char>>& board,int a,int b)
    {
        int x = 0,y = 0;
        queue<pair<int,int>> q;
        q.push({a,b});
        board[a][b]='.';
        while(!q.empty())
        {
            int a = q.front().first, b = q.front().second;
            q.pop();
            for(int k = 0;k<4;++k)
            {
                x = a+dx[k];
                y = b+dy[k];
                if(x>=0 && x<n && y>=0 && y<m && 'O'==board[x][y])
                {
                    q.push({x,y});
                    board[x][y]='.';
                }
            }
        }
    }
};